#include"BinaryTree.h"
#include"Queue.h"

BTNode* BuyBinaryTreeNode(BTDataType x)
{
	BTNode* newtree = (BTNode*)malloc(sizeof(BTNode));
	if (newtree == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	newtree->data = x;
	newtree->left = NULL;
	newtree->right = NULL;
	return newtree;
}

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* p)
{
	assert(a);
	if (a[*p] == '#')
	{
		(*p)++;
		return NULL;
	}
	BTNode* newtree = BuyBinaryTreeNode(a[*p]);
	(*p)++;
	newtree->left=BinaryTreeCreate(a, n, p);
	newtree->right = BinaryTreeCreate(a, n, p);
	return newtree;
}

void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
		return;
	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);
	free(*root);
	*root = NULL;
}

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == root->right)
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize( root->left, k - 1)+BinaryTreeLevelKSize(root->right,k-1);
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* n = BinaryTreeFind(root->left, x);
	BTNode* m = BinaryTreeFind(root->right, x);
	if (n)
		return NULL;
	else
		return m;
}

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%c  ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreePrevOrder(root->left);
	printf("%c  ", root->data);
	BinaryTreePrevOrder(root->right);
}

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
	printf("%c  ", root->data);
}

void BinaryTreeLevelOrder(BTNode* root)
{
	assert(root);
	Que q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* temp = QueueTop(&q);
		printf("%c  ", temp->data);
		QueuePop(&q);
		if (temp->left)
		{
			QueuePush(&q, temp->left);
		}
		if (temp->right)
		{
			QueuePush(&q, temp->right);
		}
	}
}

bool BinaryTreeComplete(BTNode* root)
{
	assert(root);
	Que q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (QueueTop(&q)!=NULL)
	{
		BTNode* temp = QueueTop(&q);
		QueuePop(&q);
		QueuePush(&q, temp->left);
		QueuePush(&q, temp->right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* temp = QueueTop(&q);
		if (temp != NULL)
		{
			return false;
		}
		QueuePop(&q);
	}
	return true;

}







